/*
    * Copyright (C) 2010 The Guava Authors
    *
    * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
    * in compliance with the License. You may obtain a copy of the License at
    *
    * http://www.apache.org/licenses/LICENSE-2.0
    *
    * Unless required by applicable law or agreed to in writing, software distributed under the License
   * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
   * or implied. See the License for the specific language governing permissions and limitations under
   * the License.
   */
  
  package com.google.common.collect;
  
  import static com.google.common.base.Preconditions.checkArgument;
  import static com.google.common.base.Preconditions.checkNotNull;
  
  import com.google.common.annotations.Beta;
  import com.google.common.annotations.GwtCompatible;
  import com.google.common.annotations.GwtIncompatible;
  
  import java.util.Collections;
  import java.util.NoSuchElementException;
  import java.util.Set;
  
  /**
   * A sorted set of contiguous values in a given {@link DiscreteDomain}.
   *
   * <p><b>Warning:</b> Be extremely careful what you do with conceptually large instances (such as
   * {@code ContiguousSet.create(Range.greaterThan(0), DiscreteDomain.integers()}). Certain
   * operations on such a set can be performed efficiently, but others (such as {@link Set#hashCode}
   * or {@link Collections#frequency}) can cause major performance problems.
   *
   * @author Gregory Kick
   * @since 10.0
   */
  @Beta
  @GwtCompatible(emulated = true)
  @SuppressWarnings("rawtypes") // allow ungenerified Comparable types
  public abstract class ContiguousSet<C extends Comparable> extends ImmutableSortedSet<C> {
    /**
     * Returns a {@code ContiguousSet} containing the same values in the given domain
     * {@linkplain Range#contains contained} by the range.
     *
     * @throws IllegalArgumentException if neither range nor the domain has a lower bound, or if
     *     neither has an upper bound
     *
     * @since 13.0
     */
    public static <C extends Comparable> ContiguousSet<C> create(
        Range<C> range, DiscreteDomain<C> domain) {
      checkNotNull(range);
      checkNotNull(domain);
      Range<C> effectiveRange = range;
      try {
        if (!range.hasLowerBound()) {
          effectiveRange = effectiveRange.intersection(Range.atLeast(domain.minValue()));
        }
        if (!range.hasUpperBound()) {
          effectiveRange = effectiveRange.intersection(Range.atMost(domain.maxValue()));
        }
      } catch (NoSuchElementException e) {
        throw new IllegalArgumentException(e);
      }
  
      // Per class spec, we are allowed to throw CCE if necessary
      boolean empty = effectiveRange.isEmpty()
          || Range.compareOrThrow(
              range.lowerBound.leastValueAbove(domain),
              range.upperBound.greatestValueBelow(domain)) > 0;
  
      return empty
          ? new EmptyContiguousSet<C>(domain)
          : new RegularContiguousSet<C>(effectiveRange, domain);
    }
  
    final DiscreteDomain<C> domain;
  
    ContiguousSet(DiscreteDomain<C> domain) {
      super(Ordering.natural());
      this.domain = domain;
    }
  
    @Override public ContiguousSet<C> headSet(C toElement) {
      return headSetImpl(checkNotNull(toElement), false);
    }
  
    /**
     * @since 12.0
     */
    @GwtIncompatible("NavigableSet")
    @Override public ContiguousSet<C> headSet(C toElement, boolean inclusive) {
      return headSetImpl(checkNotNull(toElement), inclusive);
    }
  
    @Override public ContiguousSet<C> subSet(C fromElement, C toElement) {
      checkNotNull(fromElement);
     checkNotNull(toElement);
     checkArgument(comparator().compare(fromElement, toElement) <= 0);
     return subSetImpl(fromElement, true, toElement, false);
   }
 
   /**
    * @since 12.0
    */
   @GwtIncompatible("NavigableSet")
   @Override public ContiguousSet<C> subSet(C fromElement, boolean fromInclusive, C toElement,
       boolean toInclusive) {
     checkNotNull(fromElement);
     checkNotNull(toElement);
     checkArgument(comparator().compare(fromElement, toElement) <= 0);
     return subSetImpl(fromElement, fromInclusive, toElement, toInclusive);
   }
 
   @Override public ContiguousSet<C> tailSet(C fromElement) {
     return tailSetImpl(checkNotNull(fromElement), true);
   }
 
   /**
    * @since 12.0
    */
   @GwtIncompatible("NavigableSet")
   @Override public ContiguousSet<C> tailSet(C fromElement, boolean inclusive) {
     return tailSetImpl(checkNotNull(fromElement), inclusive);
   }
 
   /*
    * These methods perform most headSet, subSet, and tailSet logic, besides parameter validation.
    */
   /*@Override*/ abstract ContiguousSet<C> headSetImpl(C toElement, boolean inclusive);
 
   /*@Override*/ abstract ContiguousSet<C> subSetImpl(C fromElement, boolean fromInclusive,
       C toElement, boolean toInclusive);
 
   /*@Override*/ abstract ContiguousSet<C> tailSetImpl(C fromElement, boolean inclusive);
 
   /**
    * Returns the set of values that are contained in both this set and the other.
    *
    * <p>This method should always be used instead of
    * {@link Sets#intersection} for {@link ContiguousSet} instances.
    */
   public abstract ContiguousSet<C> intersection(ContiguousSet<C> other);
 
   /**
    * Returns a range, closed on both ends, whose endpoints are the minimum and maximum values
    * contained in this set.  This is equivalent to {@code range(CLOSED, CLOSED)}.
    *
    * @throws NoSuchElementException if this set is empty
    */
   public abstract Range<C> range();
 
   /**
    * Returns the minimal range with the given boundary types for which all values in this set are
    * {@linkplain Range#contains(Comparable) contained} within the range.
    *
    * <p>Note that this method will return ranges with unbounded endpoints if {@link BoundType#OPEN}
    * is requested for a domain minimum or maximum.  For example, if {@code set} was created from the
    * range {@code [1..Integer.MAX_VALUE]} then {@code set.range(CLOSED, OPEN)} must return
    * {@code [1..∞)}.
    *
    * @throws NoSuchElementException if this set is empty
    */
   public abstract Range<C> range(BoundType lowerBoundType, BoundType upperBoundType);
 
   /** Returns a short-hand representation of the contents such as {@code "[1..100]"}. */
   @Override public String toString() {
     return range().toString();
   }
 
   /**
    * Not supported. {@code ContiguousSet} instances are constructed with {@link #create}. This
    * method exists only to hide {@link ImmutableSet#builder} from consumers of {@code
    * ContiguousSet}.
    *
    * @throws UnsupportedOperationException always
    * @deprecated Use {@link #create}.
    */
   @Deprecated public static <E> ImmutableSortedSet.Builder<E> builder() {
     throw new UnsupportedOperationException();
   }
 }